package com.chenjun.year2018.january.day12;

/**
 * href="http://www.cnblogs.com/c-cloud/p/3224788.html"
 */
public class KMP {
    /**
     * 　　1、已知前一步计算时最大相同的前后缀长度为k（k>0），即P[0]···P[k-1]；
     * 　　2、此时比较第k项P[k]与P[q],如图1所示
     * 　　3、如果P[K]等于P[q]，那么很简单跳出while循环;
     * 　　4、<b>关键！关键有木有！关键如果不等呢？？？</b>
     * 那么我们应该利用已经得到的next[0]···next[k-1]来<b>求P[0]···P[k-1]这个子串中最大相同前后缀</b>，
     * 可能有同学要问了——为什么要求P[0]···P[k-1]的最大相同前后缀呢？？？
     * 是啊！为什么呢？
     * 原因在于P[k]已经和P[q]失配了，而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同，
     * 看来P[0]···P[k-1]这么长的子串是用不了了，
     * 那么我要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]···P[j-1](j==next[k-1])，
     * 看看它的下一项P[j]是否能和P[q]匹配。如图2所示
     * *********************************************************
     * p[0]----|-p[q-k]----p[q-1]-|-p[q]-|----
     * |  ||         ||   |  ?   |
     * |-p[0]------p[k-1]-|-p[k]-|----p[q]----
     * |                  | 比较 |
     * 图一
     * **********************************************************
     * p[0]----|-p[q-k]----p[q-1]-|-p[q]-|----
     * |  ||         ||   |  !=  |
     * |-p[0]------p[k-1]-|-p[k]-|----p[q]----
     * |             ||   |      |
     * |     p[0]--p[j-1]-|-p[j]-|----p[k]----
     * 图二
     * **********************************************************
     * 比较p[q]与p[j]，(p[0]---p[j-1])是(p[0]--p[k-1])的一个公共前缀
     *
     * @param p
     * @param next
     */
    private static void makeNext(char p[], int next[]) {
        int q, k;//q:模版字符串下标；k:最大前后缀长度
        int m = p.length;//模版字符串长度
        next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
        for (q = 1, k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值
        {
            while (k > 0 && p[q] != p[k])//递归的求出P[0]···P[q]的最大的相同的前后缀长度k
                k = next[k - 1];          //不理解没关系看下面的分析，这个while循环是整段代码的精髓所在，确实不好理解
            if (p[q] == p[k])//如果相等，那么最大相同前后缀长度加1
            {
                k++;
            }
            next[q] = k;
        }
    }

    private static void kmp(char T[], char P[], int next[]) {
        int n, m;
        int i, q;
        n = T.length;
        m = P.length;
        makeNext(P, next);
        for (i = 0, q = 0; i < n; ++i) {
            while (q > 0 && P[q] != T[i])
                q = next[q - 1];
            if (P[q] == T[i]) {
                q++;
            }
            if (q == m) {
                System.out.printf("Pattern occurs with shift:%d\n", (i - m + 1));
            }
        }
    }

    public static void main(String[] args) {
        int i;
        int[] next = new int[20];
        char T[] = "ababxbababcadfdsss".toCharArray();
        char P[] = "abcdabd".toCharArray();
        kmp(T, P, next);
        for (i = 0; i < P.length; ++i) {
            System.out.printf("%d ", next[i]);
        }
        System.out.printf("\n");

    }
}
